package offer.of12;

import java.util.Arrays;

public class Solution {
//    int[][][] dp;
    boolean[][] vis;
    char[][] board;
    String word;
    public boolean exist(char[][] board, String word) {
        this.board=board;
        this.word=word;
//        dp=new int[board.length][board[0].length][word.length()];
        vis=new boolean[board.length][board[0].length];

        for (int i= 0;i< board.length;i++){
            for (int j = 0; j < board[0].length; j++) {
                if (findPath(i,j,0)){
                    return true;
                }else {
                    for (boolean[] e:vis){
                        Arrays.fill(e,false);
                    }
                }
            }
        }
        return false;
    }
    public boolean findPath(int i,int j,int position){
        vis[i][j]=true;

//        if (dp[i][j][position]==0){
            if (board[i][j]==word.charAt(position)){
                if (position==word.length()-1){
//                    dp[i][j][position]=1;
                    return true;
                }
                int[] left=new int[]{i,Math.max(i-1,0),Math.min(i+1, board.length-1),i};
                int[] right=new int[]{Math.max(j-1,0),j,j,Math.min(j+1, board[0].length-1)};
                for (int k = 0; k < left.length; k++) {
                    if (!vis[left[k]][right[k]]){
                        if (findPath(left[k], right[k],position+1)){
//                            dp[i][j][position]=1;
                            return true;
                        }
                    }
                }
            }
//            dp[i][j][position]=2;
            vis[i][j]=false;
            return false;
//        }else {
//            return dp[i][j][position]==1;
//        }
    }
}